package leetcode.jianzhioffer;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-08 14:06
 **/
public class JianZhiOffer16 {
    //迭代
    public double myPow(double x, int n) {
        //有一个int型数的最小值转成正数就会越界,所以将n转成long
        long N = n;
        return N > 0 ? quickMul(x, N) : 1 / quickMul(x, -N);
    }

    double quickMul(double x, long n) {
        double xContribute = x;
        double res = 1.0;
        while (n > 0) {
            if ((n & 1) == 1) {
                res *= xContribute;
            }

            xContribute *= xContribute;
            n /= 2;
        }
        return res;
    }

    //递归
    /*public double myPow(double x, int n) {
        return n > 0 ? quickMul(x, n) : 1.0 / quickMul(x, -n);
    }

    private double quickMul(double x, int n) {
        //除了0任何数的0次幂都为1
        if (n == 0) {
            return 1.0;
        }
        double y = quickMul(x, n / 2);
        return n % 2 == 0 ? y * y : y * y * x;
    }*/

}
